package mo.offer_special;

import java.util.ArrayList;
import java.util.List;

public class L079 {

    private List<Integer> t = new ArrayList<>();
    private List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        dfs(0, nums);
        return ans;
    }

    public List<List<Integer>> subsets2(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        ret.add(new ArrayList<>());
        for (int num : nums) {
            int len = ret.size();
            for (int i = 0; i < len; i++) {
                List<Integer> cur = new ArrayList<>(ret.get(i));
                cur.add(num);
                ret.add(cur);
            }
        }
        return ret;
    }

    private void dfs(int cur, int[] nums) {
        if (cur == nums.length) {
            ans.add(new ArrayList<>(t));
            return;
        }
        t.add(nums[cur]);
        dfs(cur+1, nums);
        t.remove(t.size()-1);
        dfs(cur+1, nums);
    }

    public static void main(String[] args) {
        L079 test = new L079();
        System.out.println(test.subsets(new int[]{1, 2, 3}));
    }

}
